package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1234 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 核心思想是双指针，滑动窗口，窗口里中的统计频次要有超过平均频率的
     * 因此窗口外的频次肯定都小于4/N
     * freq数组中的频次是窗口外的频次累计
     * 未来需要再次复习此道题目
     * @return:
     */
    class Solution {
        public int balancedString(String s) {
            if (s == null || s.length() <= 0) {
                return 0;
            }
            int N = s.length();
            int left = 0;
            int res = N;
            int[] freq = new int[26];
            for (int i = 0; i < N; i++) {
                freq[s.charAt(i) - 'A']++;
            }
            for (int right = 0; right < N; right++) {
                freq[s.charAt(right) - 'A']--;
                while (left < N && freq['Q' - 'A'] <= N / 4 && freq['W' - 'A'] <= N / 4 && freq['E' - 'A'] <= N / 4 && freq['R' - 'A'] <= N / 4) {
                    res = Math.min(res, right - left + 1);
                    freq[s.charAt(left++) - 'A']++;
                }
            }
            return res;
        }
    }


    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC1234 an = new LC1234();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
